package 股票_状态机;

import org.junit.Test;

/*
    新：-> 就是个 普通 最值DP [ 特：买/卖/未动
        i 前i天
        k 当前交易总次数 -> 第二个参数内部不减 不用if套 [ 拿/不拿 *当前curSum* 用
        01 上个 1买/2卖 [3未动：k不-1 tmp记录爷的01 ]
 */
/**

 【不要了,只看上？】

 * [0]
 * dp[i] = max(dp[i-1],xx) 怎么对应 状态/选择 ？
 * 答：
 *  状态2 <=转移= 状态1
 *
 * [1 边界]
 * dp[-1][k][0] = 0
 * 解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0 。
 * dp[-1][k][1] = -infinity
 * 解释：还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。
 * dp[i][0][0] = 0
 * 解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0 。
 * dp[i][0][1] = -infinity
 * 解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。
 *
 *  -> 体现在：
 *  dp[i][k][0] = 0;
 *  dp[i][k][1] = -prices[i];
 *
 *
 *  [2 k]
 *  k不同于i 不用管0 -> k=1 k<=K
 *  因为 i=0 也要 前一个，
 *  k=0 有是有 但我不需要算 dp[k=0] <= 因为没必要 ？
 *
 *
 *
 * =>[最终简化]
 *  原始：
 *      dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
 *      dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
 *  边界：（注意是 max边界 转化而来）
 *      dp[i][k][0] = 0
 *      dp[i][k][1] = -prices[i]
 *  k：
 *      1次/无限 -> k=1/k=k-1 消k
 *      k次 -> k=1 k<=K
 *
 *  dp普适：
 *      1 [ijk] 所有 可能 都要算 -> 因为不定哪个用呢！
 *      2 乱了用 -> 汉译 （注意 加入 中间 压缩掉的 隐藏的 k值）
 */
public class 买卖股票的最佳时机 {

    /*
        dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
        dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
    */
    public int maxProfit_one_and_wuxian(int[] prices) {
        // 1 [末索引+1]
        int[][] dp = new int[prices.length][2]; // 最大索引+1 n-1+1 1+1

        // 3 不存在的情况 （也叫 初始化边界）

        // 4
        for (int i = 0; i < prices.length; i++) {
            if(i-1 == -1){ // 就是 i=0 1个..
                dp[i][0] = 0; // 这里要 左侧 的 dpi （不要i-1了）
                dp[i][1] = -prices[i]; // 这里是 第i天 交易1次 有股 应该是-p[i]
                continue; // * 少了这句 体结束
            }

            /*
               一、 [121. 1次交易]
                   状态2 <-转移- 状态1
             */
            // sell
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            // buy
            dp[i][1] = Math.max(dp[i - 1][1], - prices[i]);

            /*
                二、 [122. 无限次数]
                    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);

                四、 [714. 无限次数 + 手续费]
                    // 因为 最后 res 要 [0] 无股的 -> 所以 在 卖出 减 手续费
                    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
                    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);

                三、 [309. 无限次数 + 冷冻期]
                    因为 k 是由 买 决定
                    所以 只 关心 //buy 即可
                    改  dp[i - 2][0] - prices[i] 即可

                    但 [i-2] 存在一个问题：
                        if(i==1) -> dp[i-2][0] = dp[-1][0] -> 没法处理，要自己距离 初化掉
                            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);

                    ->汉：
                        第i天 交易了k次 有股 <= Max 昨天有股没变、昨天没股买股
                        (但是由于冷冻期 必须不是前天买的 但是因为i=1,当前是第2天，不存在前一天 -> 所以 easy了 直接买股即可)
             */
        }

        // 2 res 要的 索引 -> 神奇 消[k]
        return dp[prices.length - 1][0];
    }

    /*
       五、 [123. 交易2次]

     */
    public int maxProfit_two(int[] prices) {
        int n = prices.length;
        int[][][] dp = new int[n][3][2]; // 012 -> 3

        for (int i = 0; i < n; i++) {
            for (int k = 1; k <=2; k++) {
                // 没开始
                if (i-1 == -1 ) {
                    // 无股 -> 利0
                    dp[i][k][0] = 0;
                    // 解释：
                    //   dp[i][0]
                    // = max(dp[-1][0], dp[-1][1] + prices[i])
                    // = max(0, -infinity + prices[i]) = 0
                    dp[i][k][1] = -prices[i]; // * 我之前算出[-1] 还少了一步Math.max比较!
                    //解释：
                    //   dp[i][1]
                    // = max(dp[-1][1], dp[-1][0] - prices[i])
                    // = max(-infinity, 0 - prices[i])
                    // = -prices[i]

                    continue; // 老少！

                }
                // sell 无股
                dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]); // 这里 k不-1 因为 只在 买 时 -> 更新 交易次数
                // buy 有股
                dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
            }
        }

        return dp[n-1][2][0];
    }

    /*
       六、 [123. 交易k次]

     */
    public int maxProfit_k(int K, int[] prices) {
        int n = prices.length;
        int[][][] dp = new int[n][K+1][2];
        for (int i = 0; i < n; i++) {
            for (int k = 1; k <= K; k++) {
                if(i-1==-1){
                    dp[i][k][0] = 0;
                    dp[i][k][1] = -prices[i];
                    continue;
                }
                dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]); // 不是k-1 因为 买时 统计 交易次数 1次即可
                dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
            }
        }
        return dp[n-1][K][0];
    }

    @Test
    public void test() {
        int[] p = new int[]{7,1,5,3,6,4};
        System.out.println("RES:" + maxProfit_one_and_wuxian(p) );
    }
}
